package leetcode;

import java.util.LinkedList;
import java.util.List;

class Solution_17 {
    public String[] keyboard = new String[]{
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz", // 9
    };
    public List<String> result = new LinkedList<>();
    public List<String> letterCombinations(String digits) {
        int length = digits.length();
        if (length == 0) return result;
        List<String> d = new LinkedList<String>();
        for (int i = 0; i < length; i++) {
            int index = digits.charAt(i) - '0';
            if (index > 10){
                return result;
            }
            d.add(keyboard[index]);
        }
        backtracking(d,0, "");
        return result;
    }
    public void backtracking(List<String> selects,int start,String res){
        if (start >= selects.size()){
            result.add(res);
            return;
        }
        String select = selects.get(start);

        for (int i = 0; i < select.length(); i++) {
            backtracking(selects,start + 1,res + select.charAt(i));
        }
    }
}